Incomplete preferences are likely to arise in real-world preference aggregation scenarios. This paper deals with determining whether an incomplete preference profile is single-peaked. This is valuable information since many intractable voting problems become tractable given singlepeaked preferences. We prove that the problem of recognizing single-peakedness is NP-complete for incomplete profiles consisting of partial orders. Despite this intractability result, we find several polynomial-time algorithms for reasonably restricted settings. In particular, we give polynomial-time recognition algorithms for weak orders, which can be viewed as preferences with indifference.

We establish an equivalence between two seemingly different theories: one is the traditional axiomatisation of incomplete preferences on horse lotteries based on the mixture independence axiom; the other is the theory of desirable gambles (bounded random variables) developed in the context of imprecise probability, which we extend here to make it deal with vector-valued gambles. The equivalence allows us to revisit incomplete preferences from the viewpoint, and with the tools, of desirability and through the derived notion of coherent lower previsions (i.e., lower expectation functionals). On this basis, we obtain new results and insights: in particular, we show that the theory of incomplete preferences can be developed assuming only the existence of a worst act--no best act is needed--, and that a weakened Archimedean axiom suffices too; this axiom allows us also to address some controversy about the regularity assumption (that probabilities should be positive--they need not), which enables us also to deal with uncountable possibility spaces; we show that it is always possible to extend in a minimal way a preference relation to one with a worst act, and yet the resulting relation is never Archimedean, except in a trivial case; we show that the traditional notion of state independence coincides with the notion called strong independence in imprecise probability (stochastic independence in the case of complete preferences)--this leads us to give much a weaker definition of state independence than the traditional one; we rework and uniform the notions of complete preferences, beliefs, values; we argue that Archimedeanity does not capture all the problems that can be modelled with sets of expected utilities and we provide a new notion that does precisely that. Perhaps most importantly, we argue throughout that desirability is a powerful and natural setting to model, and work with, incomplete preferences, even in the case of non-Archimedean problems. This leads us to suggest that desirability, rather than preference, should be the primitive notion at the basis of decision-theoretic axiomatisations. Keywords: Incomplete preferences, decision theory, expected utility, desirability, convex cones, imprecise probability.

Incomplete preferences are likely to arise in real-world preference aggregation and voting systems. This paper deals with determining whether an incomplete preference profile is single-peaked. This is essential information since many intractable voting problems become tractable for single-peaked profiles. We prove that for incomplete profiles the problem of determining single-peakedness is NP-complete. Despite this computational hardness result, we find four polynomial-time algorithms for reasonably restricted settings.

Multi-winner social choice considers the problem of selecting a slate of K options to realize some social objective. It has found application in the construction of political legislatures and committees, product recommendation, and related problems, and has recently attracted attention from a computational perspective. We address the multi-winner problem when facing incomplete voter preferences , using the notion of minimax regret to determine a  robust slate of options in the presence of preference uncertainty. We analyze the complexity of this problem and develop new exact and greedy robust optimization algorithms for its solution. Using these techniques, we also develop preference elicitation heuristics which, in practice, allow us to find near-optimal slates with considerable savings in the preference information required vis-a-vis complete votes.